/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 10
 * Time: 10:16int
 */
//牛客 斐波那契数列
public class Solution6 {
    //法一 迭代(推荐使用) 相当于空间优化版本的动态规划
    public static int Fibonacci (int n) {
        if(n == 1 || n == 2) return 1;
        int ret = 0;
        int a = 1, b = 1;
        for (int i = 3; i <= n ; i++) {
            ret = a + b;
            a = b;
            b = ret;
        }
        return ret;
    }

    //法二 递归
    public int Fibonacci1 (int n) {
        if(n == 1 || n == 2) return 1;
        return Fibonacci1 (n - 1) + Fibonacci1 (n - 2);
    }
}
